package com.kaigejava.ms.linkedlist;

import java.util.Stack;

/**
 * @author kaigejava
 * 链表相关的面试题
 * 1：获取链表中有效的个数
 * 2：查找单链表中的倒数第K个节点
 * 3：单链表的反转(腾讯面试题)
 * 4：从尾开始打印链表(2中方方：1：翻转链表后打印，2：使用栈这个数据结构)
 * 5：合并两个有序的链表，合并后任然有序
 */
public class MsLinkedList {

    /**
     * 声明头结点
     */
    MsNode hearNode = new MsNode(0,"","");

    public MsNode getHearNode(){
        return hearNode;
    }
    /***************************************************以下开始MS的**************************************/

    /**
     *  4：从尾开始打印链表
     *  使用栈这个数据结构
     * @param hearNode
     */
    public void reverwithStack(MsNode hearNode){
        if(null == hearNode.nextNode || null == hearNode.nextNode.nextNode){
            System.out.println("链表为空或者只有一个节点。不用反转");
            return;
        }
        Stack<MsNode> stack = new Stack();
        MsNode nextNode = hearNode.nextNode;
        while(null != nextNode){
            stack.push(nextNode);
            nextNode = nextNode.nextNode;
        }

        while (stack.size() > 0) {
            //stack的特点是先进后出
            System.out.println(stack.pop());
        }
    }

    /**
     * 3：单链表反转
     * 思路：
     * 1：声明循环原链表的节点
     * 2：声明用于存放反转的链表
     * 3：循环原链表的时候，每循环一个追加到新链表的前面
     * 4：循环完成后，将链表的头节点的下一个节点指向新链表的头结点的下一个节点
     * 当链表为空或者链表的第二个也为空的话，就不用反转
     * @param hearNode
     */
    public void reversetList(MsNode hearNode){
        if(null == hearNode.nextNode || null == hearNode.nextNode.nextNode){
            System.out.println("链表为空或者只有一个节点。不用反转");
            return;
        }
        //声明循环原来链表的当前节点
        MsNode curr = hearNode.nextNode;
        //声明用于存放发当前节点的下一个节点的临时变量
        MsNode currNext = null;
        //声明新链表的头节点
        MsNode reversHeardNode = new MsNode(0,"","");
        //遍历原链表
        while(null != curr){
            //用于存放当前节点的下一个节点的
            currNext = curr.nextNode;
            //将当前节点的下一个节点指向新链表头节点的下一个节点。
            curr.nextNode = reversHeardNode.nextNode;
            //将当前节点连接到新链表的头结点的下一个
            reversHeardNode.nextNode = curr;
            //当前节点后移一个[思考：这里为什么不用curr.nexe而要用个变量存放后，在指向呢？]
            //因为curr.next = reheard.next。所以，如果这里在curr = curr.next的话，会有问题的
            curr = currNext;
        }
        //循环完成后，将头节点的下一个节点指向新链表的头结点的下一个节点
        hearNode.nextNode = reversHeardNode.nextNode;

       //如果当前链表为空，或者只有一个节点，无需反转，直接返回
        /*if(hearNode.nextNode == null || hearNode.nextNode.nextNode == null) {
            return ;
        }

        //定义一个辅助的指针(变量)，帮助我们遍历原来的链表
        MsNode cur = hearNode.nextNode;
        MsNode next = null;// 指向当前节点[cur]的下一个节点
        MsNode reverseHead = new MsNode(0, "", "");
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
        //动脑筋
        while(cur != null) {
            next = cur.nextNode;//先暂时保存当前节点的下一个节点，因为后面需要使用
            cur.nextNode = reverseHead.nextNode;//将cur的下一个节点指向新的链表的最前端
            reverseHead.nextNode = cur; //将cur 连接到新的链表上
            cur = next;//让cur后移
        }
        //将head.next 指向 reverseHead.next , 实现单链表的反转
        hearNode.nextNode = reverseHead.nextNode;
*/
    }



    /**
     * 2：查找单链表中的倒数第K个节点
     * 思路：
     * 1：先遍历得到所有有效的个数
     * 2：需要获取到第K个元素的上一个元素。所以需要循环次数为 size - index 。因为是倒数的。所以需要size-index
     * 例如：size = 3.倒数第1个。那么就需要倒数第一个的上一个应该是循环了2次。那么这个2怎么得到呢？就是size-index
     * @param hearNode
     * @param index
     * @return
     */
    public MsNode findLastIndexNode(MsNode hearNode,int index){
        if(hearNode.nextNode == null){
            System.out.println("链表为空");
            return null;
        }
        //获取链表中有效的数量
        int size = this.getLength(hearNode);
        if(0== size || index >size){
            System.out.printf("不符合规则.有效的数量为:%d , index为: %d",size,index);
            return null;
        }
        //开始获取
        MsNode temp = hearNode.nextNode;
        //循环.因为是倒数第K个。所以，循环次数应该是size - index
        for (int i = 0; i < size - index; i++) {
            temp = temp.nextNode;
        }
        return temp;
    }


    /**
     * 获取链表中有效的数量。
     * 思路：非头结点+1.需要判断，如果是最后一个节点的话，不用在+1了
     * @param hearNode  一个链表的头结点
     * @return
     */
    public int getLength(MsNode hearNode){
        if(hearNode.nextNode == null ){
            System.out.println("空链表。");
            return 0;
        }
        int length = 0;
        //头结点不统计在内。所有声明头结点的下一个节点
        MsNode curnode = hearNode.nextNode;
        while (null != curnode){
            length++;
            curnode = curnode.nextNode;
        }
        return length;
    }


    /***************************************************以上开始MS的**************************************/

    /**
     * 添加
     * 思路：
     * 1：因为头节点不能动【这个一定要注意】,所以我们使用临时变量存储头节点
     * 2：怎么遍历到最后一个呢？因为不知道具体循环次数。所有用while(true)，当next为空的时候，说明当前就是最后一个，退出循环
     * 3：将当前循环的next指向需要加入的node就可以
     * @param node
     */
    public void add(MsNode node){
        //用来存储头结点的。因为头结点不能动
        MsNode tempHeard = hearNode;
        while(true){
            if(tempHeard.nextNode == null){
                //已经是最后一个了
                break;
            }
            //如果没有break,说明当前节点不是最后一个节点。所以，节点应该继续后移
            //【这一步很重要】需要将指针后移
            tempHeard = tempHeard.nextNode;
        }
        //当跳出while循环后，就得到了当前链表中最后一个节点了。所以，新加入的节点就应该等于当前节点的下一个值
        tempHeard.nextNode = node;

    }

    /**
     * 更新节点
     * 思路：
     * 约定：根据No是否相关来查找是否是一个
     * 其核心就是要找到当前节点的no=需要更新节点的no.然后进行数据更新
     * 既是：temp.no = no
     * 数据更新：
     * this.name = update.name
     * 注意：【找节点的位置和删除节点找的思路不一样】
     * @param updateNode
     */
    public void updateNode(MsNode updateNode){
       if(hearNode.nextNode == null){
            System.out.println("队列为空，不允许修改");
            return;
        }
        //声明临时节点
        MsNode temp = hearNode.nextNode;
        boolean findFlage = false;
        while (true){
            if(temp == null){
                //链表已经遍历完成
                break;
            }
            if(temp.no == updateNode.no){
                //说明找到了
                findFlage = true;
                //找到后，跳出循环
                break;
            }
            //当前节点不是需要更新的节点。指针向后移动
            temp = temp.nextNode;
        }
        //循环完成后，就知道了节点。然后进行更新
       if(findFlage){
           //查找到。就进行更新
           temp.nickName = updateNode.nickName;
           temp.name = updateNode.name;
       }else {
           System.out.printf("编号为 %d的节点没有查找到。未更新数据\n",updateNode.no);
       }


    }


    /**
     * 删除节点
     * 思路：
     * 其核心是要找到需要删除节点的上一个节点。找到后，将上一个节点的next指向删除节点的下一个节点就可以了
     * 既是：temp.next.no = no 表示当前节点的下一个节点就等于删除节点了。返回这个节点
     * 删除操作：
     * 将当前节点下一个节点（就是要删除的节点）的下一个节点指向当前节点的下一个节点既可以了。
     * 既是：temp.next = temp.next.next;
     * @param delNode
     */
    public void delNode(MsNode delNode){
        int no = delNode.no;
        MsNode temp = hearNode;
        // 标志是否找到待删除节点的
        boolean flag = false;
        while(true) {
            //已经到链表的最后
            if(temp.nextNode == null) {
                break;
            }
            if(temp.nextNode.no == no) {
                //找到的待删除节点的前一个节点temp
                flag = true;
                break;
            }
            //temp后移，遍历
            temp = temp.nextNode;
        }
        //判断flag
        if(flag) {
            //找到
            //可以删除
            temp.nextNode = temp.nextNode.nextNode;
        }else {
            System.out.printf("要删除的 %d 节点不存在\n", no);
        }
    }

    /**
     * 查看链表
     */
    public void showAll(){
        MsNode temp = hearNode.nextNode;
        if(temp == null){
            System.out.println("队列为空，不允许操作");
            return ;
        }
        while (true){
            if(null == temp){
                break;
            }
            //显示
            System.out.println(temp);
            //指针向下移动一个
            temp = temp.nextNode;
        }
    }


    /**
     * 根据序号按照顺序插入
     * 思路：
     * 循环判断当前节点的下一个节点的no，如果大于需要插入节点的no.则要插入节点的下一个节点等当前节点的下一个节点;当前节点的下一个节点等于要插入的节点
     * 如果当前节点的序号和插入节点的序号相等。就抛出异常
     */
    public void addPushByNo(MsNode addNode){
        //头结点
        MsNode temp = hearNode;
        //标识要插入的节点是否存在
        boolean addNodeFlag = false;
        if(null == temp.nextNode){
            //列表为空。直接插入
            hearNode.nextNode = addNode;
            return;
        }
        while (true){
            if(temp.nextNode.no > addNode.no){
                break;
            }else if(temp.nextNode.no == addNode.no){
                addNodeFlag = true;
                break;
            }
            //都没有的话，指针向后移动
            temp = temp.nextNode;
        }
        if(addNodeFlag){
            System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", addNode.no);
        }else{
            //将要插入的节点，插入到队列中
            //当前节点的下一个节点大于了要插入的节点。所以，要插入节点的下一个节点就是当前节点的下一个节点
            addNode.nextNode = temp.nextNode;
            //当前节点的下一个节点就等于要插入的节点
            temp.nextNode = addNode;
        }
    }
}


/**
 * @author kaigejava
 *  内部类 node节点
 */
class MsNode{

    /**
     * 编号
     */
    public int no;

    /**
     * 名字
     */
    public String name;

    /**
     * 昵称
     */
    public String nickName;

    /**
     * 下一个节点
     */
    public MsNode nextNode;

    public MsNode(int no,String name,String nickName){
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }


    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName  +
                '}';
    }
}
